package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/13 11:31 下午
 */
public class 剑指_Offer_10_II_青蛙跳台阶问题 {

    /**
     * 动态规划 + 类斐波拉契数列
     */
    int MOD = 1000000007;
    public int numWays(int n) {
        if (n < 2) {
            return 1;
        }
        int first = 1, second = 1, temp;
        for (int i = 2; i <= n; i++) {
            temp = (first + second)%MOD;
            first = second;
            second = temp;
        }
        return second;
    }
}
